#pragma once

struct ListNode 
{
	int val;
	ListNode* next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode* next) : val(x), next(next) {}
	
};

 class Solution
 {
 public:
     ListNode* swapPairsNoRn(ListNode* head)
     {
         if (head == nullptr || head->next == nullptr)
             return head;
         ListNode* l1 = nullptr, * l2 = nullptr;
         l1 = head;
         l2 = head->next;
         ListNode* NewHead = nullptr;
         ListNode* start = nullptr;
         while (l1 != nullptr && l2 != nullptr)
         {
             ListNode* end = l2->next;
             if (NewHead == nullptr)
             {
                 NewHead = l2;
             }
             if (start)
                 start->next = l2;
             l2->next = l1;
             l1->next = end;

             start = l1;
             l1 = l1->next;
             if (l1)
             {
                 l2 = l1->next;
             }
             else
                 break;
         }
         return NewHead;
     }

     ListNode* swapPairs(ListNode* head)
     {
         if(head == nullptr || head->next == nullptr)
         {
             return head;
         }
         ListNode* tmp = swapPairs(head->next->next);
         ListNode* ret = head->next;
         head->next->next = head;
         head->next = tmp;
         return ret;
     }
 };